#include <iostream>
using namespace std;
namespace DateStruct
{
	struct BinaryTreeDate
	{
		int key;
		BinaryTreeDate *parent;
		BinaryTreeDate *left;
		BinaryTreeDate *right;
		bool Color;//false 为black,true 为 red
		BinaryTreeDate(int Key) :key(Key), left(nullptr), right(nullptr), parent(nullptr), Color(true)
		{}
	};

	struct BinaryTreeDate_OS
	{
		size_t SIZE;
		int key;
		BinaryTreeDate_OS *parent;
		BinaryTreeDate_OS *left;
		BinaryTreeDate_OS *right;
		bool Color;//false 为black,true 为 red
		BinaryTreeDate_OS(int Key) :key(Key), left(nullptr), right(nullptr), parent(nullptr), Color(true), SIZE(0)
		{}
	};

	BinaryTreeDate *TreeSearch(BinaryTreeDate *root, int val)
	{
		if (root == nullptr)
			return root;

		if (val > root->key)
			return TreeSearch(root->right, val);
		else if (val < root->key)
			return TreeSearch(root->left, val);

		return root;
	}

	BinaryTreeDate *TreeSearchNotRecursion(BinaryTreeDate *root, int val)
	{
		while (root != nullptr && root->key != val)
		{
			if (val > root->key)
				root = root->right;
			else
				root = root->left;
		}
		return root;
	}

	BinaryTreeDate *TreeMaxSearch(BinaryTreeDate *root)
	{
		while (root->right != nullptr)
			root = root->right;

		return root;
	}

	BinaryTreeDate *TreeMinSearch(BinaryTreeDate *root)
	{
		while (root->left != nullptr)
			root = root->left;

		return root;
	}

	BinaryTreeDate *TreeMinRecursionSearch(BinaryTreeDate *root)
	{
		if (root->left == nullptr)
			return root;
		else
			return TreeMinRecursionSearch(root->left);
	}

	BinaryTreeDate *TreeMaxRecursionSearch(BinaryTreeDate *root)
	{
		if (root->right == nullptr)
			return root;
		else
			return TreeMaxRecursionSearch(root);
	}

	BinaryTreeDate *TreeNodeSuccessor(BinaryTreeDate *Node)
	{
		if (Node->right != nullptr)
			return TreeMinRecursionSearch(Node->right);//向下查找

		//向上查找
		BinaryTreeDate *parent = Node->parent;
		while (parent != nullptr && parent->right == Node)
			//若为左节点则表明parent就是其大节点集合中最小的一个
		{
			Node = parent;
			parent = parent->parent;
		}
		return parent;
	}

	BinaryTreeDate *TreeNodePredecessors(BinaryTreeDate *Node)
	{
		if (Node->left != nullptr)
			return TreeMaxRecursionSearch(Node->left);//向下查找

		BinaryTreeDate *parent = Node->parent;
		while (parent != nullptr && parent->left == Node)
			//若为右节点则表明parent就是其小节点集合中最大的一个
		{
			Node = parent;
			parent = parent->parent;
		}
		return parent;
	}

	void TreeInsert(BinaryTreeDate *&root, BinaryTreeDate *NewNode)
	{
		BinaryTreeDate *p = root;
		BinaryTreeDate *parent = nullptr;
		while (p != nullptr)
		{
			parent = p;
			if (NewNode->key > p->key)
				p = p->right;
			else
				p = p->left;
		}
		NewNode->parent = parent;
		if (parent == nullptr)
			root = NewNode;
		else if (NewNode->key > parent->key)
			parent->right = NewNode;
		else
			parent->left = NewNode;
	}

	//更改结点
	void TreeTransition(BinaryTreeDate *&root, BinaryTreeDate *Node, BinaryTreeDate *T)
	{
		if (Node->parent == nullptr)//表明要删除的结点为root结点
			root = T;
		else
		if (Node->parent->left == Node)
			Node->parent->left = T;
		else
			Node->parent->right = T;

		if (T != nullptr)
			T->parent = Node->parent;
	}

	void TreeDeleteNode(BinaryTreeDate *&root, BinaryTreeDate *Node)
	{
		if (Node->left == nullptr)
			TreeTransition(root, Node, Node->right);
		else
		if (Node->right == nullptr)
			TreeTransition(root, Node, Node->left);
		else
		{
			//左右两棵树都不为nullptr
			//更改的为右子树
			BinaryTreeDate *Successor = TreeMinRecursionSearch(Node->right);//获得后继
			if (Successor->parent != Node)//表明Successor->left为空,Successor->right可能不为空
			{
				TreeTransition(root, Successor, Successor->right);//处理Successor->right
				//这个时候Successor已经变为单独Node，Successor->left

				Successor->right = Node->right;//更改
				Successor->right->parent = Successor;
			}
			TreeTransition(root, Node, Successor);//处理Node的parent Node使其指向 Successor并让Successor->parent = Node->parent

			//处理Node->left结点
			Successor->left = Node->left;
			Successor->left->parent = Successor;
		}
		delete Node;//释放结点z
	}

	void TreeInsertNotRecursion(BinaryTreeDate *&root, BinaryTreeDate *NewNode)
	{
		BinaryTreeDate *T = root;
		if (T == nullptr)
			root = NewNode;
		else
		{
			if (NewNode->key > T->key)
				TreeInsertNotRecursion(T->right, NewNode);
			else
				TreeInsertNotRecursion(T->left, NewNode);
			if (NewNode->parent == nullptr)//只有第一次赋值时才是其真正parent结点
				NewNode->parent = T;
		}
	}

	void RightRotate(BinaryTreeDate *&root, BinaryTreeDate *Node)
	{
		if (Node->left == nullptr)
			return;

		BinaryTreeDate *Left = Node->left;
		Node->left = Left->right;
		if (Left->right != nullptr)
			Left->right->parent = Node;
		
		Left->parent = Node->parent;

		if (Node->parent == nullptr)
			root = Left;
		else 
		if (Node->parent->left == Node)
			Node->parent->left = Left;
		else
			Node->parent->right = Left;

		Left->right = Node;
		Node->parent = Left;

	}

	void LeftRotate(BinaryTreeDate *&root, BinaryTreeDate *Node)
	{
		if (Node->right == nullptr)//要左转的结点右子树为空则不需要转换
			return;

		BinaryTreeDate *Right = Node->right;//获得右子树
		
		Node->right = Right->left;//改变要左转结点右子树的指向
		if (Right->left != nullptr)
			Right->left->parent = Node;//更改右子树的左子树，与上一步对应
		
		Right->parent = Node->parent;//更改右子树的父结点指向
		if (Node->parent == nullptr)//更改左转结点父结点指向与上一步对应
			root = Right;
		else if (Node->parent->left == Node)
			Node->parent->left = Right;
		else
			Node->parent->right = Right;

		Right->left = Node;//更改右子树的左子树结点
		Node->parent = Right;//与上一步对应
	}

	void TreeRB_Insert(BinaryTreeDate *&root, BinaryTreeDate *Node)
	{
		if (root == nullptr)
		{
			root = Node;
			root->Color = false;
		}
		else
		{
			//false为black,true 为 red,为空则为black
			TreeInsert(root, Node);
			while (Node->parent != nullptr && Node->parent->Color == true)
			{
				if (Node->parent = Node->parent->parent->left)
				{
					 BinaryTreeDate *Npp = Node->parent->parent->right;
					 if (Npp != nullptr && Npp->Color == true)
					{
						 Node->parent->Color = false;
						 Node->parent->parent->Color = true;
						 Npp->Color = false;
						 Node = Node->parent->parent;
					}
					else
					{
						if (Node == Node->parent->right)
						{
							Node = Node->parent;
							LeftRotate(root, Node);
						}
						Node->parent->Color = false;
						Node->parent->parent->Color = true;
						RightRotate(root, Node->parent->parent);
					}
				}
				else
				{
					BinaryTreeDate *Npp = Node->parent->parent->left;
					if (Npp != nullptr && Npp->Color == true)
					{
						Node->parent->Color = false;
						Npp->Color = false;
						Node->parent->parent->Color = true;
						Node = Node->parent->parent;
					}
					else
					{
						if (Node->parent->left == Node)
						{
							Node = Node->parent;
							RightRotate(root, Node);
						}
						Node->parent->Color = false;
						Node->parent->parent->Color = true;
						LeftRotate(root, Node->parent->parent);
					}
				}
				root->Color = false;//更改根节点为黑，为了符合性质根节点为黑，另一方面出作为循环的出路
			}
		}
	}
	
	void RB_Delete(BinaryTreeDate *&root, BinaryTreeDate *Node)
	{
		BinaryTreeDate *y = Node;
		BinaryTreeDate *x = nullptr;//记录要删除Node的左右子Node，要删除节点只可能是单枝
		bool Color = y->Color;
		if (y->left == nullptr)
		{
			x = y->right;//指向剩余结点头
			TreeTransition(root, Node, Node->right);//从树中脱离Node并更改Node本来位置为Node->right
		}
		else
		if (y->right == nullptr)
		{
			x = y->left;
			TreeTransition(root, Node, Node->left);
		}
		else
		{
			//删除Node左右不为空
			y = TreeMinRecursionSearch(Node->right);//重新指定真正删除Node
			Color = y->Color;
			x = y->right;//pointer remove node son node

			if (y->parent == Node && x != nullptr)
				x->parent = Node;
			else
			{
				TreeTransition(root, y, y->right);
				y->right = Node->right;
				y->right->parent = y;
			}
			TreeTransition(root, Node, y);//更替原删除结点
			y->left = Node->left;
			y->left->parent = y;
			y->Color = Node->Color;
		}
		if (Color == false)
			RB_DELETE_FIXUP(root, x);//x为导致平衡性质破坏关键点
	}
	void RB_DELETE_FIXUP(BinaryTreeDate *&root, BinaryTreeDate *Node)
	{

	}

	BinaryTreeDate_OS *OS_Select(BinaryTreeDate_OS *&root, size_t n)
	{
		//获得顺序树秩为n的Node
		BinaryTreeDate_OS *Node = root;

		size_t nTemp = Node->left->SIZE + 1;

		while (nTemp != n && GetNIL() != Node)
		{
			if (nTemp > n)
				Node = Node->left;
			else
			{
				n -= nTemp;
				Node = Node->right;
			}
			nTemp = Node->left->SIZE + 1;//重新更新当前节点顺序位
		}

		return Node;
	}

	size_t OS_RANK(BinaryTreeDate_OS *&root, BinaryTreeDate_OS *Node)
	{
		//获得Node的秩
		if (Node == GetNIL())
			return 0;
		
		size_t SIZE = Node->left->SIZE + 1;
		while (Node != root)
		{
			if (Node == Node->parent->right)
				SIZE += Node->parent->left->SIZE + 1;

			Node = Node->parent;
		}
		return SIZE;
	}

	BinaryTreeDate_OS *OS_GetKeyNode(BinaryTreeDate_OS *&root, int Key)
	{
		//获得Key值相等的Node
		BinaryTreeDate_OS *Node = root;
		while (Node->key != Key && GetNIL() != Node)
		{
			if (Node->key > Key)
				Node = Node->left;
			else
				Node = Node->right;
		}

		return Node;
	}

	size_t OS_KEY_RANK(BinaryTreeDate_OS *&root, int Key)
	{
		//获得Key值相等的秩
		return OS_RANK(root,OS_GetKeyNode(root, Key));
	}

	BinaryTreeDate_OS *GetNIL()
	{
		static BinaryTreeDate_OS NIL(0);
		return &NIL;
	}

	void OS_RBLeftRotate(BinaryTreeDate_OS *&root, BinaryTreeDate_OS *Node)
	{
		BinaryTreeDate_OS *y = Node->right;
		Node->right = y->left;
		if (y->left != GetNIL())
			y->left->parent = Node;

		y->parent = Node->parent;
		if (Node->parent == GetNIL())
			root = y;
		else
		if (Node->parent->left == Node)
			Node->parent->left == y;
		else
			Node->parent->right = y;

		y->left = Node;
		Node->parent = y;
		
		y->SIZE = Node->SIZE;
		Node->SIZE = Node->left->SIZE + Node->right->SIZE + 1;
	}

	void OS_RIGHTROTATE(BinaryTreeDate_OS *&root, BinaryTreeDate_OS *Node)
	{
		BinaryTreeDate_OS *y = Node->left;
		Node->left = y->right;

		if (y->right != GetNIL())
			y->right->parent = Node;

		y->parent = Node->parent;
		if (Node->parent == GetNIL())
			root = y;
		else
		if (Node->parent->left == Node)
			Node->parent->left = y;
		else
			Node->parent->right = y;

		y->right = Node;
		Node->parent = y;

		y->SIZE = Node->SIZE;
		Node->SIZE = Node->left->SIZE + Node->right->SIZE + 1;
	}

}
int main()
{
	using namespace DateStruct;
	BinaryTreeDate *p = nullptr;
	BinaryTreeDate *Node = new BinaryTreeDate(23);
	BinaryTreeDate *Node1 = new BinaryTreeDate(22);
	BinaryTreeDate *Node2 = new BinaryTreeDate(20);
	BinaryTreeDate *Node3 = new BinaryTreeDate(10);
	TreeRB_Insert(p, Node);
	TreeRB_Insert(p, Node1);
	TreeRB_Insert(p, Node2);
	TreeRB_Insert(p, Node3);
	delete Node;
	delete Node1;
	delete Node2;
	delete Node3;
	return 0;
}